'''
Created on Nov 24, 2009
# Problem Set 3 (Part I)
# Name: Noah Spahn
# Collaborators: magnus89
# Time: 2:30
'''
from string import *

def countSubStringMatch(target,key):
    '''
    Returns a tuple of indexes for matching instances of key in the provided target
    target: string
    key: integer
    '''
    matchCount = 0
    length = len(target)
    start = 0
    while start < len(target):
        location = find(target[start:],key)
        if location > -1:
            matchCount += 1
            start = start + location + 1
        else:
            start += 1
    return matchCount

def countSubStringMatchRecursive(target,key):
    '''
    Returns a tuple of indexes for matching instances of key in the provided target, finds the solution iteratively
    target: string
    key: integer
    '''
    i = 0 
    position = find(target,key)
    if position !=-1:
        i+=1
        target = target[position+1:]
        i += countSubStringMatchRecursive(target,key)
    return i

t = "atgacatgcacaagtatgcatatgcatgc"
k = "atgc"
print "count Sub-String Match:",countSubStringMatch(t,k)
print "count Sub-String Match Recursive:",countSubStringMatchRecursive(t,k)

# References
#    http://docs.python.org/tutorial/introduction.html#strings
#    http://stackoverflow.com/questions/509211/good-primer-for-python-slice-notation
#    http://docs.python.org/library/stdtypes.html